package SwordOffer;

public class Sword_Offer_10_II {

    public int numWays(int n) {
        if (n <= 1) {
            return n;
        }
        int pre1 = 1, pre2 = 1;
        for (int i = 2; i <= n; i++) {
            int temp = (pre1 + pre2) % 1000000007;
            pre1 = pre2;
            pre2 = temp;
        }
        return pre2;
    }

    public static void main(String[] args) {
        Sword_Offer_10_II model = new Sword_Offer_10_II();
        System.out.println(model.numWays(100));
        System.out.println(model.numWays(7));
    }
}
